/*
* @Description: 
* @Author: 李龙生
* @Date: 2022-07-08
* @LastEditTime: 2022-07-08
* @LastEditors: Please set LastEditors
*/
/**
 * @func 快速排序
 * @desc
 * 1.定义快排的数组参数
 * 2.检查数组中的长度，如果小于等于1则直接返回
 * 3.选择枢轴，将其与原始数组分开，并定义两个空数组来存储两个子集
 * 4.遍历数组，小于主元的元素放入左子集中，大于主元的元素放入右子集中
 * @param {
 *  arr: Array<number>
 * }
 * @return {
 *  arr: Array<number>
 * }
 */

let arr = [86, 24, 64, 48, 15, 30, 90, 49]

const quickSort = (arr) => {
    // 检查数组中的长度，如果小于等于1则直接返回
    if (arr.length <= 1) {
        return arr
    }
    // 选择枢轴，将其与原始数组分开，并定义两个空数组来存储两个子集
    let pivotIndex = Math.floor(arr.length / 2)
    let pivot = arr.splice(pivotIndex, 1)[0] // 这个操作会删除中间枢纽
    let left = []
    let right = []
    // 遍历数组，小于主元的元素放入左子集中，大于主元的元素放入右子集中
    for (let index = 0; index < arr.length; index++) {
        const ele = arr[index];
        if (ele < pivot) {
            left.push(ele)
        } else {
            right.push(ele)
        }
    }
    return quickSort(left).concat([pivot], quickSort(right))
}

const sortArr = quickSort(arr)
console.log("sortArr", sortArr);

/**
 * @func 二分查找
 * @desc
 * 1.以整个数组的中间元素作为搜索键开始。
 * 2.如果搜索键的值等于项目，则返回搜索键的索引。
 * 3.或者搜索键的值小于区间中间的项，则将区间缩小到下半部分。
 * 4.否则，将其缩小到上半部分。
 * 5.否则，将其缩小到上半部分。
 * @param {
 *  arr: Array<number>
 * }
 * @return {
 *  number
 * }
 */
function binarySearch(arr, x) {
    let l = 0;
    let r = arr.length - 1;
    let mid;
    while (r >= l) {
        // 取中间值
        mid = l + Math.floor((r - l) / 2);
        // 找到则直接返回中间索引
        if (arr[mid] == x) {
            return mid;
        }
        // 如果中间值大于查询的值，说明在左半部分，令右边边界值为中间索引 - 1
        if (arr[mid] > x) {
            r = mid - 1;
        }
        // 如果中间值大于查询的值，说明在右半部分，令左边边界值为中间索引 + 1
        if (arr[mid] < x) {
            l = mid + 1;
        }
    }
    return -1;
}

const selectedIndex = binarySearch([1, 2, 3, 5, 8, 11, 30, 50], 8)
console.log("selectedIndex", selectedIndex)

/**
 * @func 反转单链表
 * @desc
 * 1.以整个数组的中间元素作为搜索键开始。
 * 2.如果搜索键的值等于项目，则返回搜索键的索引。
 * 3.或者搜索键的值小于区间中间的项，则将区间缩小到下半部分。
 * 4.否则，将其缩小到上半部分。
 * 5.否则，将其缩小到上半部分。
 * @param {
 *  head: Node {
 *      value,
 *      next
 *  }
 * }
 * @return {
 *  prev
 * }
 */

// 定义链表结构
class Node {
    constructor(value) {
        this.value = value
        this.next = null
    }
}

class LinkList {
    constructor() {
        this.head = new Node("head")
    }
    find(item) {
        let currNode = this.head;
        while (currNode != null && currNode.value != item) {
            currNode = currNode.next;
        }
        return currNode;
    }
    insert(newEl, item) {
        let newNode = new Node(newEl);
        let current = this.find(item);
        //元素不存在，返回false
        if (current == null) return false;
        newNode.next = current.next;
        current.next = newNode;
        return true;
    }
}

let linkList = new LinkList()
linkList.insert(1, "head")
linkList.insert(2, 1)
linkList.insert(3, 2)
linkList.insert(4, 3)
console.log("linkList", linkList);

// 反转链表
const reveseList = head => {
    let pre = null
    let next = null
    let current = head

    while (current !== null) {
        // 存下当前节点的下一个节点
        next = current.next
        // 当前节点的下一个节点变成前节点，达到反转效果
        current.next = pre
        // 前节点变成当前节点
        pre = current
        // 当前节点变成下一个节点
        current = next
    }
    return pre
}

const _list = reveseList(linkList.head)
console.log("_list", _list);

/**
 * @func 解析模板语法
 * @desc
 * 1.如果问题涉及括号或其他对称结构，则相关解决方案很可能与堆栈有关。
 * 2.我们的想法是：遍历整个字符串：
 * 3.如果找到左括号，则将其添加到堆栈中。
 * 4.如果找到右括号，则弹出堆栈顶部的一个元素，并确定当前的右括号是否匹配它。
 * @param {
 *  str: string
 *  }
 * }
 * @return {
 *  boolean
 * }
 */
const getKey = (stack) => {
    let keyStr = ""
    let startIndex = -1 // 开始括号索引
    const stcLen = stack.length
    for (let j = 0; j < stcLen; j++) {
        const keyEl = stack.pop();
        if (keyEl.value === "{") {
            startIndex = keyEl.index
            // 清空栈,预防{ aa{bb} }
            stack = []
            break
        }
        keyStr = keyEl.value + keyStr
    }
    return {
        keyStr,
        startIndex,
    }
}

const getStrKeys = str => {
    if (!str) {
        return false
    }
    // 定义一个栈
    let stack = []
    // 定义一个接key的数组
    let keyList = []
    const len = str.length
    for (let index = 0; index < len; index++) {
        // cache
        const ch = str[index];
        // 匹配到"}"开始才出栈
        if (ch === "}") {
            keyList.push({
                ...getKey(stack),
                endIndex: index,
            })
        }
        stack.push({
            index: index,
            value: ch
        })
    }
    return keyList
}

const tempalte = (str, obj) => {
    const strKeyInfo = getStrKeys(str)
    const keyList = Object.keys(obj)
    let resStr = str
    let steps = 0
    strKeyInfo.forEach(e => {
        // 去除字符串前后空格
        let key = e.keyStr.trim()
        steps = resStr.length - str.length // 步数差
        // 如果对象中有这个key，则进行替换
        if (keyList.includes(key)) {
            resStr = resStr.slice(0, e.startIndex + steps) + obj[key] + resStr.slice(e.endIndex + 1 + steps, resStr.lenght)
        }
    })
    return resStr
}

const tempalteObj = {
    name: "李龙生",
    age: "24"
}
let str = "我叫{name }, 我今年{  age }岁"
str = tempalte(str, tempalteObj)
console.log("str", str);